package Aim_at_Offer;
/*
 *  Author: Ksxy
 *  Date: 2018/3/25
 *  Version: 1.0
 *  Description:
 */

import java.util.Arrays;

public class RebuildBinaryTree {

    public static TreeNode reConstructBinaryTree(int [] pre, int [] in) {

            if(pre == null || in == null){
                throw new IllegalArgumentException("pre Array or in Array is null");
            }

            if(pre.length != in.length){
                throw new IllegalArgumentException("pre Array is not as long as in Array");
            }

            TreeNode root = new TreeNode(pre[0]);
            int root_index = -1;
            for(int i=0; i < in.length; i++){
                if(pre[0] == in[i]){
                    root_index = i;
                    break;
                }
            }
            if(in.length == 1) return root;
            //ex pre = {1,2,4,7,3,5,6,8}, in = {4,7,2,1,5,3,8,6}
            int[] leftTreeIn = Arrays.copyOfRange(in, 0, root_index);   //{4,7,2}
            int[] rightTreeIn = Arrays.copyOfRange(in, root_index+1, in.length);  //{5,3,8,6}
            int[] leftTreePre = Arrays.copyOfRange(pre, 1, 1+leftTreeIn.length);  //{2,4,7}
            int[] rightTreePre = Arrays.copyOfRange(pre, pre.length-rightTreeIn.length, pre.length); //{3,5,6,8}

            TreeNode left = reConstructBinaryTree(leftTreePre, leftTreeIn);
            TreeNode right = reConstructBinaryTree(rightTreePre, rightTreeIn);
            root.left = left;
            root.right = right;
            return root;
    }

    public static class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode(int x) { val = x; }
     }

    public static void main(String[] args) {
        int[] pre = new int[]{1,2,4,3,5,6};
        int[] in = new int[]{4,2,1,5,3,6};
        TreeNode root = reConstructBinaryTree(pre, in);


    }

    public static void printBinaryTree(TreeNode root){

    }
}
